package algorithm.middle;

import java.util.*;

/**
 * 你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
 * <p>
 * 如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。
 * <p>
 * 文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一个或者多个小写英文字母。
 */
public class RemoveSubfolders1233 {

    public List<String> res = new ArrayList();

    public List<String> removeSubfolders(String[] folder) {
        Map<String, Node> outMap = new HashMap<>();
        for (String s : folder) {
            //解析string
            String[] split = s.split("/");
            //最外层文件夹
            Node pre = new Node();
            pre.setName(split[1]);
            Map<String, Node> tempMap = outMap;
            tempMap.putIfAbsent(pre.getName(), pre);
            for (int i = 1; i < split.length; i++) {
                Node cur = tempMap.get(split[i]);
                if (cur == null) {
                    cur = new Node();
                    cur.setName(split[i]);
                    tempMap.put(cur.getName(), cur);
                }
                tempMap = cur.getMap();
                if (i == split.length - 1) {
                    cur.setExist(true);
                }
            }
        }
        for (Node value : outMap.values()) {
            loops("", value);
        }
        return res;
    }

    public void loops(String str, Node node) {
        str = str + "/" + node.getName();
        if (node.isExist() ) {
            res.add(str);
            return;
        }
        for (Node value : node.getMap().values()) {
            loops(str, value);
        }
    }

    public List<String> removeSubfolders2(String[] folder) {
        Arrays.sort(folder);
        List<String> ans = new ArrayList<>();
        ans.add(folder[0]);
        for (int i = 1; i < folder.length; ++i) {
            int m = ans.get(ans.size() - 1).length();
            int n = folder[i].length();
            if (m >= n || !(ans.get(ans.size() - 1).equals(folder[i].substring(0, m)) && folder[i].charAt(m) == '/')) {
                ans.add(folder[i]);
            }
        }
        return ans;
    }




    public static void main(String[] args) {
        List<String> list = new RemoveSubfolders1233().removeSubfolders(new String[]{"/a/b/c","/a/b/ca","/a/b/d"});
        System.out.println(list);
    }

    static class Node {
        String name;
        Map<String, Node> map = new HashMap<>();
        boolean exist = false;

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Map<String, Node> getMap() {
            return map;
        }

        public void setMap(Map<String, Node> map) {
            this.map = map;
        }

        public boolean isExist() {
            return exist;
        }

        public void setExist(boolean exist) {
            this.exist = exist;
        }
    }
}
